//
// Created by liushuai on 2020/4/3.
//
#include "lengthOfLongestSubstring.h"
int lengthOfLongestSubstring(std::string s) {
  const int N = static_cast<int>(s.size());
  if (N == 0) return 0;
  int dp[N] = {};
  int hash[26] = {};
  std::fill(hash, hash + 26, -1);
  int result = -1;
  for (int i = 0; i < N; i++) {
    if (i == 0) {
      dp[0] = 1;
      hash[s.at(i) - 'a'] = i;
    } else {
      if (hash[s.at(i) - 'a'] == -1) {
        dp[i] = dp[i - 1] + 1;
        hash[s.at(i) - 'a'] = i;
      } else {
        int d = i - hash[s.at(i) - 'a'];
        if (d <= dp[i - 1])
          dp[i] = d;
        else {
          dp[i] = dp[i - 1] + 1;
        }
        hash[s.at(i) - 'a'] = i;
      }
    }
    if (result < dp[i]) result = dp[i];
  }
  return result;
}

// int lengthOfLongestSubstring(string s) {
//   map<char, int> char_dict;
//   int start = 0;
//   int max_num = 0;
//   int size = s.size();
//   for (int end = 0; end < size; end++) {
//     char current_char = s.at(end);
//     if (!char_dict.count(current_char))  // 不存在字符，更新索引
//       char_dict[current_char] = end;
//     else {
//       start = max(
//           char_dict[current_char] + 1,
//           start);  //
//           存在字符，起点为重复字符索引的下一位，防止重复出现的输出的下一位比当前的start小
//       char_dict[current_char] = end;
//     }
//
//     max_num = std::max(end - start + 1, max_num);
//   }
//   return max_num;
// }
